A portion of the disclosure of this patent document contains material which is subject copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates generally to a system and method for scaling image resolution conversion, and specifically to a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation.
2. Description of Related Art
A wide variety of applications today utilize digital images, where many of these applications have different resolution requirements. In order to perform several applications using the same digital image, the resolution of the digital image must be converted between the resolution requirements of the various applications. Some multi-function peripheral devices have been developed for performing several of these digital image applications, such as scanning, storing, copying, faxing, and printing images. In performing these functions, the resolution required for each of these applications is typically different from the other applications. For instance, the resolution of scanner, printer, and fax standards are typically quite different. International standards define the resolution of faxed documents, while scanners and printers often possess resolutions which are a function of the individual capabilities of the respective devices. In order to support applications having varying resolution requirements, it is necessary to perform resolution conversion between the multiple applications. It is common for a scanner to have a resolution of 300 dpi, while some printers have resolutions of 600 dpi. In order to make the printed image the same size as the image scanned by the scanner, a resolution conversion of 300 dpi to 600 dpi is required.
Scaling methods are utilized to perform this resolution conversion in order to scale the size of an image between respective applications. Previous scaling methods have included the use of a fixed ratio of resolution conversion between an input resolution and an output resolution. For instance, a 1280xc3x971280 pixel input box could be scaled down to a 640xc3x97640 pixel output box. Other scaling methods have further used a set of fixed resolution conversions, wherein a user may select a desired scaling of an image from a set of predetermined resolutions incremented in steps, such as image size reductions of 90%, 80%, 70%, etc. These prior scaling methods were limited to predefined incremental steps and did not allow a user to variably select the resolution conversion to more precise values depending upon the needs of the user.
Several scaling methods have been developed to provide a variably selectable resolution conversion, where the particular resolution conversion selected is a function of the number of input pixels and the number of output pixels. One such scaling method is the nearest neighbor algorithm, where each output pixel is mapped from its closest neighboring input pixel. The closest neighbor is determined as a function of the spacing between the input pixels and the spacing between the output pixels. After the input pixels have been mapped to output pixels using the closest neighbor algorithm, all remaining unmapped input pixels which do not closely neighbor an output pixel are removed. These deleted input pixels create image distortion and aliasing in the output image. Another scaling method known as linear interpolation improves on the nearest neighbor algorithm by forming every output pixel as a weighted average of the two closest respective input pixels. An example of linear interpolation scaling is shown in FIG. 1. Linear interpolation scaling prevents pixel dropping for certain scaling factors above 50%. However, for resolution conversions less than 50%, linear interpolation degenerates into the closest neighbor algorithm where certain input pixels are deleted. As can be seen from FIG. 1, input pixels 2, 5, and 8 do not contribute to the output pixels when converting from nine input pixels to four output pixels. Thus, aliasing and distortion problems also arise with certain applications of the linear interpolation scaling method.
In order to perform resolution conversion for all resize factors without information loss through pixel dropping, each input pixel from an image must contribute to the output pixels. One such lossless technique is known as ""textbook correct"" scaling or DSP scaling, where multi-rate digital signal processing is used to perform the scaling. FIG. 2 illustrates an example of DSP scaling, where nine input pixels are scaled down to four output pixels. Initially, a set of upsampled pixels are generated from the input pixels using an interpolator, where each input pixel is multiplied by a coefficient value and added together with other values. The resulting upsampled pixel values are then stored in memory elements. Filtering and decimation is then performed on the upsampled pixel values to generate the output pixels. A decimator multiplies the upsampled pixels by a set number of coefficients called filter taps and sums the products to produce a single output pixel. The decimator coefficients are calculated based upon DSP theory to produce output pixels with minimal aliasing.
While the DSP scaling method minimizes aliasing for any resize factor, there are also several drawbacks of the DSP scaling method. The first drawback is caused by the directly proportional relationship of the resize factor to the number of upsampled pixels. For example, if a user wanted to resize 1000 pixels down to 999 pixels, then almost one million upsampled pixels are required to be generated in real time with each one of these upsampled pixels being stored in a memory element. Thus, a great deal of memory is required to store the upsampled pixels as well as requiring fast clock cycles to pipeline the upsampling process in a real-time manner. Another problem results from the large number of decimator coefficients that are required to be calculated for each resize factor, because calculating decimator coefficients for every resize factor is difficult and expensive to implement in hardware. Thus, the resolution conversion achieved by the DSP scaling method depends upon the number of memory elements available and the number of calculations performed, resulting in a large amount of computational complexity, processing time, and memory required to produce unaliased output pixels through DSP scaling.
There is clearly a need for a system and method for implementing multi-level image resolution conversion to efficiently produce unaliased output image pixels in a cost-effective, real-time manner. Moreover, there is a need for a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation which performs image scaling for all resize factors while reducing the number of complex calculations, processing time, and amount of memory required for performing the desired resolution conversion.
It is a primary object of the present invention to overcome the aforementioned shortcomings associated with the prior art.
The present invention provides a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation scaling.
The present invention further provides a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation which performs image scaling for all resize factors without the need to store a large number of upsampled intermediate pixel values.
The present invention further provides a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation which minimizes the number of complex calculations, the amount of processing time, and the amount of memory required for performing the resolution conversion.
These as well as additional advantages of the present invention are achieved by providing a system and method for implementing multi-level resolution conversion (MLRC) of an image efficiently using linear interpolation. Based upon a desired resolution conversion, a relationship between the number of input pixels of an input image and the number of output pixels of a converted image is determined. The system includes an equation generator for automatically generating the values of the output pixels in a real-time manner as a function of the input pixels and the desired resolution conversion. The equation generator uses linear interpolation to determine each output pixel as a weighted average of its closest respective input pixels, where each of the input pixels are utilized in forming the output pixels. As the input pixel values are received by the resolution conversion system, the output pixel values are generated in real-time at a rate required for the output resolution. In this manner, a large number of intermediate complex calculations are not required to be generated and stored in memory in order to produce the output pixel values.
In order to minimize the complexity of the calculations performed by the MLRC system, the values used in generating the output pixel values are normalized to values within a predetermined range utilized by the MLRC system. The normalized values are further shifted within the predetermined range in order to perform the function of division. When implementing linear interpolation, a floating point divider is normally required for performing division functions when calculating the weighted average of the input pixels to produce the output pixels. The MLRC system of the present invention normalizes and shifts its values in order to eliminate the need for the continual use of a floating point divider. The method of implementing multi-level image resolution conversion of the present invention allows the system to be implemented in an efficient and economical manner by eliminating the continual use of a floating point divider, minimizing the amount of memory required to perform the resolution conversion, and simplifying the calculations necessary for performing the resolution conversion.